前言

在当今流行的MVVM框架如Vue.js、React框架中，一个重要的特性就是virtual Dom。通过其核心算法diff，高效的将数据层的变化反映在视图层中。受到了livoras同学文章的启发，下面将从三部分介绍virtual DOM与diff算法。通过了解该算法，有助于理解当今流行前端框架的原理，也能从中复习到有关深度优先搜索的算法知识。

virtual DOM的必要性

受制于以往标准的拖累，DOM规范已经十分臃肿。举个栗子：

我们先看看目前DOM的附带的属性。

1
2
3
4
5
6
const el = document.createElement('div')
let	keys = ""
for (let key in el){
	keys = keys + key + " "
}
console.log(keys)	/*align title lang translate dir dataset hidden tabIndex accessKey draggable spellcheck autocapitalize contentEditable isContentEditable inputMode offsetParent offsetTop offsetLeft offsetWidth offsetHeight style innerText 等235个*/

仅仅一个DOM元素就附带了如此多的属性，那么在大规模重构的时候的效率应当是相当低下的。

假设我们找火锅店。要迅速根据条件排列已有的数据，通过重绘DOM无法做到在大数据量的情况下快速在视图层体现出来。

img

因此，我们可以尝试将DOM简化至我们需要的最小模型。举一个栗子，假如我们要实现以下结构：

1
2
3
4
5
6
<ul>
    <li>item1</li>
    <li>item2</li>
    <li>item3</li>
    <li>item4</li>
</ul>

只需要提供以下数据：

1
2
3
4
5
6
7
8
9
10
11
12
const ul = {
    tagName: "ul",
    props: {
        id: "list"
    },
    children: [
        {tagName: "li", props: {class: "item"}, children: ["item1"]},
        {tagName: "li", props: {class: "item"}, children: ["item2"]},
        {tagName: "li", props: {class: "item"}, children: ["item3"]},
        {tagName: "li", props: {class: "item"}, children: ["item4"]}
    ]
}

然后，根据所提供的数据结构，就可以通过我们定义的render函数将其绘制出来，一旦数据发生改变，我们根据变动的情况，使用diff算法求得需要改动DOM的最小部分，将其存入patch缓存中。最后通过patch函数，将diff求得的改动应用到DOM树上。

以上，就是virtual DOM实现高效修改DOM树的基本原理。通过总结我们也发现，vitural DOM的实现是在目前规范限制下进行工程化的妥协。

render函数

那么，有了以上提供的ul标签的数据原型，如何将其转化为真正的DOM树呢？

只需要调用最基本的DOM API即可实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//element为vitural DOM的基本类，包含标签名、属性、子节点三个基本属性
class element {
    constructor(object) {
        this.tagName = object.tagName
        this.props = object.props
        this.children = object.children
    }

    render() {
        let el = document.createElement(this.tagName)
        //遍历vitural DOM的属性，传给真正的DOM
        for (let propName in this.props) {
            let propValue = this.props[propName]
            el.setAttribute(propName, propValue)
        }
        let children = this.children || []
        children.forEach(child => {
            let childEl
            //如果子节点也是虚拟DOM，递归渲染
            if (child instanceof element) {
                childEl = child.render()
                //如果是字符串，直接构建文本节点
            } else {
                childEl = document.createTextNode(child)
            }
            el.appendChild(childEl)
        })
        return el
    }
}

这样，我们就实现了一个最基本的vitural DOM，已经可以实现从数据到视图的转换。现在，只需要稍加修改刚才的ul数据结构，使其符合要求，就可以渲染：

1
2
3
4
5
6
7
8
9
10
11
12
13
const ul = {
    tagName: "ul",
    props: {
        id: "list"
    },
    children: [
        //子节点也为一个vitural DOM类
        new element({tagName: "li", props: {class: "item"}, children: ["item1"]}),
        new element({tagName: "li", props: {class: "item"}, children: ["item2"]}),
        new element({tagName: "li", props: {class: "item"}, children: ["item3"]}),
        new element({tagName: "li", props: {class: "item"}, children: ["item4"]})
    ]
}

最后，调用render实现渲染：

1
2
3
let ele = new element(ul),
    ulRoot = ele.render()
document.body.appendChild(ulRoot)

img

下一节，我们讲讲核心的diff算法和patch函数